//堆排序

#pragma once

//把 a[s..m] 调整为大顶堆
//假设除 a[s]z 之外，其他元素都符合大顶堆的定义
template <typename E>
void HeapAjust(E a[], int s, int m)
{
    E tmp = a[s];
    for(int j=2*s+1; j<=m; j=2*s+1){
        if(j<m && a[j+1]>a[j])
            j++;
        if(a[j] <= tmp)
            break;
        a[s] = a[j];
        s = j;
    }
    a[s] = tmp;
}

//堆排序
template <typename E>
void HeapSort(E a[], int n)
{
    //建立大顶堆
    for(int i=(n-3)/2; i>=0; i--)
        HeapAjust(a, i, n-1);
    //继续堆排序
    for(int i=n-1; i>0; i--){
        std::swap(a[0], a[i]);
        HeapAjust(a, 0, i-1);
    }
}